#define _CRT_SECURE_NO_WARNINGS 1
#include<iostream>
#include<vector>
#include<queue>
#include<unordered_map>
using namespace std;

class Solution {
public:
    int minMutation(string startGene, string endGene, vector<string>& bank) {
        char change[4] = { 'A', 'C', 'G', 'T' };
        queue<string> q;
        q.push(startGene);
        unordered_map<string, int> vis;
        vis[startGene]++;
        auto isInBank = [&](string& s)->bool {
            for (int i = 0; i < bank.size(); i++) {
                if (s == bank[i]) return true;
            }
            return false;
            };

        int ret = 0;
        while (!q.empty()) {
            int ct = q.size();
            ret++;
            while (ct--) {
                string front = q.front();
                q.pop();
                for (int i = 0; i < 8; i++) {
                    bool isChange[128] = { false };
                    isChange[front[i]] = true;
                    for (int j = 0; j < 4; j++) {
                        if (isChange[change[j]]) continue;
                        string tmp = front;
                        tmp[i] = change[j];
                        if (!vis.contains(tmp) && isInBank(tmp)) {
                            if (tmp == endGene) return ret;
                            q.push(tmp);
                            vis[tmp]++;
                        }
                    }
                }
            }
        }
        return -1;
    }
};

int minMutation(string startGene, string endGene, vector<string>& bank) {
    if (startGene == endGene) return 0;

    char changes[4] = { 'A', 'C', 'G', 'T' };
    unordered_set<string> vis;
    unordered_set<string> Bank(bank.begin(), bank.end());
    if (!Bank.count(endGene))
        return -1;

    queue<string> q;
    q.push(startGene);
    vis.insert(startGene);

    int ret = 0;
    while (!q.empty()) {
        int ct = q.size();
        while (ct--) {
            string front = q.front();
            q.pop();
            if (front == endGene)
                return ret;

            for (int i = 0; i < 8; i++) {
                char currentChar = front[i];
                for (auto ch : changes) {
                    if (currentChar != ch) {
                        string tmp = front;
                        tmp[i] = ch;
                        if (!vis.count(tmp) && Bank.count(tmp)) {
                            q.push(tmp);
                            vis.insert(tmp);
                        }
                    }
                }
            }
        }
        ret++;
    }
    return -1;
}